﻿<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<link href="CSS/main.css" rel="stylesheet" type="text/css" />
<link href="CSS/style3.css" rel="stylesheet" type="text/css" />
<link href="CSS/Layer.css" rel="stylesheet" type="text/css" />
<title>LPA* - hoangvp 2010</title>
</head>

<body>
<script type="text/javascript" src="JS/priority_queue.js"></script>
<script type="text/javascript" src="JS/MathHelpers.js"></script>
<script type="text/javascript" src="JS/AJAX.js"></script>
<script type="text/javascript" src="JS/DOM.js"></script>
<script type="text/javascript" src="JS/layer.js"></script>
<?php
require_once 'Map.class.php';

$x = new Map("map.txt");
$x->printMap();
$x->generateJSCode2();
generateJSDebugCode($DEBUG_);
?>

<script type="text/javascript">
heuristicFunction = diagonalAndEuclid;
//heuristicFunction = manhattan;

function isBetter(a, b){
	return isBetterKey(a.key, b.key);
}

/*
 * Hàm calculateKey(s)
	k2 = min{g[s], rhs[s])
	k1 = k2 + h(s, s-goal)
	return {k1, k2}
 */
function calculateKey(s){
	 var k2 = min(s.cost, s.rhs);
	 var k1 = k2 + s.heuristic;
	 return new QueueKey(k1, k2);
 }

function changeKey(s){
	var newKey = calculateKey(s);
	s.key.k1 = newKey.k1;
	s.key.k2 = newKey.k2;
}
 
 function isBetterKey(key1, key2){
	 if(key1.k1 < key2.k1){
		 return BETTER;
	 } else if(key1.k1 == key2.k1 && key1.k2 < key2.k2){
		 return BETTER;
	 } else {
		 return WORSE;
	 }
 }

 function getKey(k){
	 return "("+k.key.k1+", "+k.key.k2+") ";
 }

/*
 * Hàm init()
	U = HĐƯT rỗng
	Xét mọi đỉnh s thuộc S
		rhs[s] = g[s] = ∞
	rhs[s-start] = 0
	U.Push(s-start, calculateKey(s-start))
 */
function init(){
	queue = new PriorityQueue({cmpFunc : isBetter});
	queue.displayOne = displayOneElementInQueue;
	//Không cần đặt rhs[s] = g[s] = ∞ vì trong lúc khởi tạo map, đã đặt rồi!
	queue.push(globalStart);
	globalStart.rhs = 0;	
	//Khởi tạo thêm 1 bản đồ lưu vết
	traceMap = new Array();
	for(var i=0; i<m; ++i){				
		traceMap[i] = new Array(n);			
	}

	initHValue(globalFinish.x, globalFinish.y);
	changeKey(globalStart);
	//log("start key = "+getKey(globalStart));
	setRHS(globalStart.x, globalStart.y, 0);
}

/*
 * Hàm updateVertex(u)
	Nếu u không phải xuất phát
	rhs[u] = min(g[s']+c(s', u)) với s' thuộc Pred(u)
	Nếu u nằm trong U
		U.Remove(u)
	Nếu g[u] != rhs[u]
		U.Push(u, calculateKey(u))	
 */
function updateVertex(u){
	if(u.status == IN_OPEN_SET){
		if(u.cost == u.rhs){
			queue.remove(u);
			u.status = IN_CLOSED_SET;
		} else {
			changeKey(u);
		}
	} else if(u.cost != u.rhs){
		changeKey(u);
		queue.push(u);
		u.status = IN_OPEN_SET;
	}
}

function minPred(u){
	var list = new Array();
	for(var i=0; i<aroundLength; ++i){
		var x = u.x + around[i][0];
		var y = u.y + around[i][1];
		list[i] = new NewCost(x, y, INFINITY);
		if(doesPathExist(x, y, u.x, u.y)){
			//logDebug("\t\t\tTồn tại đường đi từ (" + x + ", " + y + ") tới ("+u.x+", "+u.y+")");
			var t = map[x][y];
			/*
			if(turn > 0){
				log("("+x+", "+y+", "+t.cost+"+"+costToMove(t.x, t.y, u.x, u.y)+") -> ("+u.x+", "+u.y+")");
			}
			*/
			if(t.cost < INFINITY) {
				list[i].cost = t.cost + costToMove(x, y, u.x, u.y);
			}
		} else if(!isFinish(x, y) || !walkable(x, y)){
			list[i].cost = INFINITY + sqrt2 + 1;
		}
	}
	
	/*
	for(var i=0; i<aroundLength; ++i){
		log("\t\t("+list[i].x+", "+list[i].y+", "+list[i].cost+")");
	}
	*/
	
	var minGC = list[0];
	for(var i=1; i<aroundLength; ++i){
		if(minGC.cost > list[i].cost){
			minGC = list[i];
		}			
	}
	//logDebug("\t\tMinPred("+u.x+", "+u.y+") = ("+minGC.x+", "+minGC.y+")");	
	return map[minGC.x][minGC.y];
}

/*
 * Hàm computeShortestPath()
	while(U.TopKey() < calculateKey(s-goal) hoặc rhs[s-goal] != g[s-goal])
		u = U.Pop()
		Nếu g[u] > rhs[u]
			g[u] = rhs[u]
			Với mỗi s thuộc Succ(u)
				updateVertex(s)
		Nếu không //tức là g[u] < rhs[u]
			g[u] = ∞
			Với mỗi s thuộc Succ(u)
				updateVertex(s)
			updateVertex(u)
 */
function computeShortestPath(){		
	var startTime = new Date();
	var found  = false;			
	loopsCount = 0;
	expandCount = 0;		
	while(!queue.isEmpty()){
		if(isBetterKey(queue.top().key, calculateKey(globalFinish))==WORSE && globalFinish.rhs == globalFinish.cost){
			break;
		}
		++loopsCount;
		var u = queue.top();
		logDebug("TopKey = "+getKey(u)+" KeyGoal = " + getKey(globalFinish));		
		setTimeout('fillRed('+u.x+', '+u.y+');', SPEED*loopsCount);
		logDebug("("+u.x + ", "+u.y+"): g="+u.cost+", rhs="+u.rhs+", h="+u.heuristic+", k="+getKey(u));
		if(u.cost > u.rhs){			
			u.cost = u.rhs;
			queue.pop();
			u.status = IN_CLOSED_SET;
			for(var i=startIndex; i<aroundLength; ++i){				
				var x = u.x + around[i][0];
				var y = u.y + around[i][1];
				if(doesPathExist(u.x, u.y, x, y)){
					logDebug("\tMở rộng tới ("+x+" "+y+")");
					var s = map[x][y];
					var costIfMoveFromU = getExactNumDigits(u.cost + costToMove(u.x, u.y, x, y), 2);
					if(s.rhs > costIfMoveFromU){
						s.rhs = costIfMoveFromU;
						traceMap[x][y] = u;
						logDebug("\tĐặt ("+x+", "+y+") tới từ ("+u.x+", "+u.y+") với rhs = "+ s.rhs);
						updateVertex(s);
						var statements ='fillYellow('+x+', '+y+');setRHS('+x+', '+y+', '+s.rhs+');setF('+x+', '+y+', '+s.key.k1+');'; 										
						setTimeout(statements, SPEED*loopsCount + DELAY);						
					}														
					++expandCount;		
				}
			}
		} else {			
			u.cost = INFINITY;			
			for(var i=startIndex; i<=aroundLength; ++i){
				var x = u.x + around[i][0];
				var y = u.y + around[i][1];				
				if(doesPathExist(u.x, u.y, x, y)){
					logDebug("\tMở rộng tới ("+x+" "+y+")");
					var s = map[x][y];					
					if(!isStart(s)){
						var t = minPred(s);
						 if(doesPathExist(t.x, t.y, x, y)) {
							s.rhs = getExactNumDigits(t.cost + costToMove(t.x, t.y, x, y), 2);
							traceMap[x][y] = t;
							updateVertex(s);
							var statements ='fillYellow('+x+', '+y+');setRHS('+x+', '+y+', '+s.rhs+');setF('+x+', '+y+', '+s.key.k1+');'; 										
							setTimeout(statements, SPEED*loopsCount + DELAY);
						 }						 
					}														
					++expandCount;						
				}
			}		
		}
		setTimeout('setG('+u.x+', '+u.y+', '+u.cost+');setRHS('+u.x+', '+u.y+', '+u.rhs+');setF('+u.x+', '+u.y+', '+u.key.k1+');', SPEED*loopsCount);
		queue.adjust();

		/*
		logDebug("OPEN SET:");
		queue.display();
		*/
	}	

	if(globalFinish.cost == globalFinish.rhs && globalFinish.g != INFINITY){		
		found = true;
	}

	var finishTime = new Date();
	//Trace path
	if(found){
		//alertDebug("Đã tìm thấy đường đi");
		tracePath(found, traceMap, loopsCount);
	}
	
	/*
	log("Trace map");
	var q = "";	
	for(var i=0; i<m; ++i){				
		for(var j=0; j<n; ++j){
			if(traceMap[i][j]){			
				log("(" + i + ", " + j + ") come from (" +traceMap[i][j].x + ", " + traceMap[i][j].y + ")");
			}
			q += "("+i+", "+j+", "+map[i][j].cost+", "+map[i][j].rhs+") ";
		}		
		q += "\n";
	}
	log(q);
	*/	
	statistic(++turn, globalFinish.cost, loopsCount, expandCount, finishTime.getTime() - startTime.getTime());

	cleanUp();
}

function cleanUp() {
	while(!queue.isEmpty()) {		
		var u = queue.pop();
		var t = minPred(u);
		u.cost = u.rhs = getExactNumDigits(t.cost + costToMove(t.x, t.y, u.x, u.y), 2);
		traceMap[u.x][u.y] = t;
		updateVertex(u);
	}
}
		
function displayOneElementInQueue(u){
	logDebug("\t("+u.x + ", "+u.y+"): g="+u.cost+", rhs="+u.rhs+", h="+u.heuristic+", k="+getKey(u));
}

/*
 * Hàm main()
	init()
	lặp lại khi nào còn cần tìm đường
		computeShortestPath()
		Chờ tới khi thay đổi trọng số
		Với mỗi cạnh (u, v) bị thay đổi trọng số
			Lưu c(u, v) mới
			updateVertex(v)
 */
var changedVerticesArray = new Array();
function updateChanging(){	
	globalFinish.cost = INFINITY;
	globalFinish.rhs = INFINITY;
	changeKey(globalFinish);
	setG(globalFinish.x, globalFinish.y, INFINITY);	
	setRHS(globalFinish.x, globalFinish.y, INFINITY);	
	setF(globalFinish.x, globalFinish.y, globalFinish.key.k1);
		
	clearNavigation();
	//log("Updating....");	
	while(changedVerticesArray.length > 0){
		var u = changedVerticesArray.pop();
		terrain[u.x][u.y] = u.cost;
		if(u.cost == 0) {	//c-old > c-new <=> turn to space			
			var t = minPred(u);
			 if(doesPathExist(t.x, t.y, u.x, u.y)){
				map[u.x][u.y].rhs = getExactNumDigits(t.cost + costToMove(t.x, t.y, u.x, u.y), 2);
				setRHS(u.x, u.y, map[u.x][u.y].rhs);
				traceMap[u.x][u.y] = t;
				logDebug("Đặt ("+u.x+", "+u.y+") tới từ ("+t.x+", "+t.y+") với rhs = " + map[u.x][u.y].rhs);
				updateVertex(map[u.x][u.y]);
			 }
			for(var i = startIndex; i<aroundLength; ++i){
				var x = u.x + around[i][0];
				var y = u.y + around[i][1];
				if(walkable(x, y) && !isFinish(x, y)){
					var cell = map[x][y];
					if(!isStart(cell)){
						var costIfMoveFromU = getExactNumDigits(map[u.x][u.y].cost + costToMove(u.x, u.y, x, y), 2);
						if(cell.rhs > costIfMoveFromU){
							cell.rhs = costIfMoveFromU;
							traceMap[x][y] = map[u.x][u.y];
							logDebug("Đặt ("+x+", "+y+") tới từ ("+u.x+", "+u.y+") với rhs = " + costIfMoveFromU);
						}
					}
					updateVertex(cell);
					var statements ='fillYellow('+x+', '+y+');setG('+x+', '+y+', '+cell.cost+');setRHS('+x+', '+y+', '+cell.rhs+');setF('+x+', '+y+', '+cell.key.k1+');'; 										
					eval(statements);
				}
			}			
		} else {	//c-old < c-new <=> turn to obstacle			
			for(var i = startIndex; i<aroundLength; ++i){
				var x = u.x + around[i][0];
				var y = u.y + around[i][1];
				if(walkable(x, y) && !isFinish(x, y)){					
					var cell = map[x][y];					
					if(traceMap[x][y] == map[u.x][u.y]){
						if(!isStart(cell)){
							var t = minPred(cell);
							if(doesPathExist(t.x, t.y, cell.x, cell.y)){
								cell.rhs = getExactNumDigits(t.cost + costToMove(t.x, t.y, cell.x, cell.y), 2);
								logDebug("Đặt ("+x+", "+y+") tới từ ("+t.x+", "+t.y+") với rhs = " + cell.rhs);
								traceMap[x][y] = t;
								updateVertex(cell);
							}
						}
					}					
					var statements ='fillYellow('+x+', '+y+');setG('+x+', '+y+', '+cell.cost+');setRHS('+x+', '+y+', '+cell.rhs+');setF('+x+', '+y+', '+cell.key.k1+');'; 										
					eval(statements);
				}
			}
		}
	}	
	queue.adjust();	

	/*
	logDebug("OPEN SET:" + queue.getSize());
	queue.display();
	*/	
	
	//log("Done!");
}

function didVertexChange(u){
	var cvaLength = changedVerticesArray.length;
	for(var i=0; i<cvaLength; ++i){		
		if(nodesEqual(u, changedVerticesArray[i])){
			return i;
		}
	}
	return -1;
}
 
function search(){	
	var f = document.route;
	var fx = f.fromX.value;
	var fy = f.fromY.value;
	var tx = f.toX.value;
	var ty = f.toY.value;
	var startChange = (!isStart(map[fx][fy]) && map[fx][fy].status != IN_OPEN_SET && turn>0) ? true : false;
	var finishChange = (!isFinish(map[tx][ty]) && turn>0) ? true : false;		
	globalStart = map[fx][fy];
	globalFinish = map[tx][ty];
	if(turn == 0){
		init();
	}
	if(startChange){
		alert("Ô xuất phát đã thay đổi! LPA* không sử dụng được các thông tin có trước nên phải thực hiện lại từ đầu như A*\nKhông thực hiện yêu cầu tìm đường!");
		return;
	}
	if(finishChange){		
		heuristicWasInitialized = false;
	}
	if(!heuristicWasInitialized){
		initHValue(globalFinish.x, globalFinish.y);
	}
	
	computeShortestPath();	
}

function changeTerrain(a){
	if(a){
		beginChangeTerrain();	
	} else {
		endChangeTerrain();
	}
}

function beginChangeTerrain(){
	changeCellFunc();
	document.searchFrm.searchBtn.disabled = "disabled";	
}

var onclickFuncs = [];
function changeCellFunc(){
	if(document.searchFrm.changeBtn.checked){
		//Change new onclick functions
		for(var i=0; i<m; ++i){
			onclickFuncs[i] = [];
			for(var j=0; j<n; ++j){
				var t = getMapCell(i, j);
				onclickFuncs[i][j] = t.getAttribute("onclick");
				t.setAttribute("onclick", "toogleCell("+i+", "+j+");");				
			}
		}
	} else {
		//Load original onclick functions
		for(var i=0; i<m; ++i){
			for(var j=0; j<n; ++j){
				getMapCell(i, j).setAttribute("onclick", onclickFuncs[i][j]);
			}
		}
		onclickFuncs.length = 0;
	}
}

function toogleCell(x, y){	
	var t = getMapCell(x, y);
	if(t.className == "wall"){
		t.className = "";
		terrain[x][y] = 0;
	} else {
		t.className = "wall";
		terrain[x][y] = 1;
	}
	var i = didVertexChange(map[x][y]);
	if(i > -1){
		changedVerticesArray.splice(i, 1);
	} else {
		changedVerticesArray.push(new NewCost(x, y, terrain[x][y]));
	}
}

function endChangeTerrain(){
	updateChanging();
	changeCellFunc();
	document.searchFrm.searchBtn.disabled = "";	

	var s = "";
	for(var i=0; i<m; ++i){
		for(var j=0; j<n; ++j){
			s += terrain[i][j] + " ";
		}
		s += "\n";
	}
	s += "\n";
	logDebug(s);
}

function clearNavigation(){	
	for(var i=0; i<m; ++i){
		for(var j=0; j<n; ++j){
			var t = getMapCell(i, j);
			switch (t.className){
				case "n":
				case "ne":
				case "nw":
				case "w":
				case "s":
				case "se":
				case "sw":
				case "e":
					t.className = "exm";
				default: break;
			}
			t.style.backgroundColor = "#FFF";
		}
	}
}
</script>
<form name="searchFrm">
	<input type="button" name="searchBtn" value="Bắt đầu" onclick="searchBtnOnclickFunc(this);" />
	<input type="button" name="resetBtn" value="Mới" onclick="window.location.reload();" /><br />
	<input type="checkbox" name="changeBtn" onclick="changeTerrain(this.checked);" /> Thay đổi bản đồ 
	<input type="button" name="saveBtn" value="Lưu bản đồ" onclick="save();" />
</form>
<div id="cost"></div>
<div>
<table id="statisticTable" border="1">
	<tr>
		<th>Lượt</th>		
		<th>Chi phí</th>
		<th>Số đỉnh được xét</th>
		<th>Số đỉnh được mở rộng</th>
		<th>Thời gian (miligiây)</th>
	</tr>
</table>
<textarea id="log" rows="30" cols="100"></textarea></div>
<br/><input type="checkbox" onclick="if(this.checked) showArrowMap(); else hideArrowMap();"/>Bật/tắt hướng di chuyển
<script type="text/javascript">
document.searchFrm.searchBtn.disabled = "";
document.searchFrm.changeBtn.checked = false;
</script>
</body>
</html>
